package com.cjm.algorithm.queue;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个循环数组nums(nums[nums.length - 1])的下一个元素是nums[0]),
 * 返回nums中每个元素的“下一个更大的元素”
 * 数字x的下一个更大的元素是按数组遍历顺序， 这个数字之后的第一个比它更大的数，
 * 这意味着你应该循环地搜索它的下一个
 * 更大的数。如果不存在， 则输出-1。
 */
public class NextGreaterElements503 {
    public int[] nextGreaterElements(int[] nums) {
        if (nums.length == 1) {
            return new int[]{-1};
        }
        Map<Integer, Integer> db = new HashMap<>();
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if (db.get(cur) != null) {
                res[i] = db.get(cur);
            }
            int j = i + 1;
            while (true) {
                if (j > nums.length - 1) {
                    j = 0;
                }
                if (j == i) {
                    res[i] = -1;
                    db.put(cur, -1);
                    break;
                }
                int num = nums[j];
                if (num > cur) {
                    res[i] = num;
                    db.put(cur, num);
                    break;
                }
                if (++j == i) {
                    res[i] = -1;
                    db.put(cur, -1);
                    break;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        NextGreaterElements503 xx = new NextGreaterElements503();
        int[] ints = xx.nextGreaterElements(new int[]{1});
        System.err.println("ok");
    }
}